---
title: "数的划分"
created: 2025-11-28
tags:
  - 算法
---

# 数的划分

## 题目 [数的划分](https://www.luogu.com.cn/problem/P1025)

![[image-c8efb4d1.png]]

## 思路分析

从n中选k个数 组合型枚举 但是这里不一样的是 他两个位置上的数可以重复 仅是顺序不能颠倒上做了限制

所以这里枚举的时候 下一位无需从i+1处枚举 直接从i开始即可

仅加位数不够的剪枝只能过3/5

发现题目还有个sum的要求 那么就可以把它也做参数传入 进行一个剪枝

居然还被卡了 过4/5

看了题解发现 tm这是dp的题

噶写多了dfs 看不出来dp了

震惊的是dfs居然能基本过 （dp白学了 bushi）

但是这个dp不太好懂 就这样写吧

也有一个很牛的dfs剪枝ac了

虽然**dfs**没有**dp**快，但是这道题数据很小如果在比赛中**dp**和**dfs**同样能过那最好还是用**dfs**，因为**dfs**的思路简单不容易错而且代码好写方便改错。这里因为要考虑到不重复，所以可以按升序记录每一次划分：记录上一次划分所用的数，保证当前划分所用数不小于上次划分所用分数，当划分次数等于k时比较该次划分所得总分是否与**n**相同并记录次数。

有一个不得不做的剪枝就是枚举当前划分所用分数时应该从**last**(上次划分所用分数)枚举到**sum+i\*(k-cur)<=n**为止，因为之后划分的分数一定大于或等于当前划分所用分数。这个剪枝不做的话不仅会**TLE**，在**TLE**之前就爆栈**RE**了

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

int n,k,cnt;

void dfs(int last,int sum,int cur){

	if(cur==k){

		if(sum==n)

			cnt++;

		return;

	}

    //for(int i=last;sum+i*(k-cur)<=n;i++)

	for(int i=last;sum+i<=n;i++)

		dfs(i,sum+i,cur+1);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	dfs(1,0,0);

	cout<<cnt<<endl;

	return 0;

}

//其实就是说 sum剪枝的地方放在dfs之前 而不是dfs之后

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=210,M=10;

int a[N];

int path[M];

int res;

int n,k;

void dfs(int u,int start,int sum){

	if(sum>n)	return;

	if(u+n-start<k)	return;

	if(u>k){

		if(sum==n){

			res++;

		}

		return;

	}

	for(int i=start;i+sum<=n;i++){

		path[u]=i;

		dfs(u+1,i,sum+i);

		path[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		a[i]=i;

	dfs(1,1,0);

	cout<<res<<endl;

	return 0;

}
```

## 代码实现

3/5

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=210,M=10;

int a[N];

int path[M];

int res;

int n,k;

void dfs(int u,int start){

	if(u+n-start<k)	return;

	if(u>k){

		int sum=0;

		for(int i=1;i<=k;i++)

			sum+=path[i];

		if(sum==n){

//			for(int i=1;i<=k;i++)cout<<path[i]<<" ";cout<<endl;

			res++;

		}

		return;

	}

	for(int i=start;i<=n;i++){

		path[u]=i;

		dfs(u+1,i);//可以重复选 但有顺序 所以从i开始即可

		path[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		a[i]=i;

	dfs(1,1);

	cout<<res<<endl;

	return 0;

}
```

4/5

```cpp
#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

const int N=210,M=10;

int a[N];

int path[M];

int res;

int n,k;

void dfs(int u,int start,int sum){

	if(sum>n)	return;

	if(u+n-start<k)	return;

	if(u>k){

		if(sum==n){

//			for(int i=1;i<=k;i++)cout<<path[i]<<" ";cout<<endl;

			res++;

		}

		return;

	}

	for(int i=start;i<=n;i++){

		path[u]=i;

		dfs(u+1,i,sum+i);

		path[u]=0;

	}

}

int main()

{

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	cin>>n>>k;

	for(int i=1;i<=n;i++)

		a[i]=i;

	dfs(1,1,0);

	cout<<res<<endl;

	return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[迷宫|迷宫]] 🏠 [[00-刷题理模型]] ➡️ [[组合型（n中选m 不考虑顺序）|组合型（n中选m 不考虑顺序）]]